#include "train.h"

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        int x = 0, n = pushed.size(); //入栈的元素个数
        stack<int>s;
        for (int i = 0; i < n; i++) //依次判断出栈序列每一位是否合法
        {
            if (s.empty() || s.top()!=popped[i]) 
            {
                while (x < pushed.size() && pushed[x]!= popped[i])//入栈的当前元素不等于出栈的当前元素
                {
                    s.push(pushed[x]);
                    x += 1;
                }

                if (x == pushed.size()) return false;
                s.push(pushed[x]);
                x += 1;
            }
            s.pop();
        }
        return true;
    }
};